Currently, humans have analytical abilities superior to those of machine-based analysis in various fields, such as object recognition, knowledge representation, reasoning, learning, natural language processing, etc. Accordingly, to mechanically imitate or surpass the human way of thinking, a complex computation method must be performed, and thus significant difficulties are entailed.
As an example of these difficulties, to imitate or surpass the human ability to perform visual recognition, an accurate solution to the optimization problem of a machine vision system is required.
A method of performing quantum-mechanical computation by using quantum computing was proposed to overcome the complex computational problem of machine vision.
As an example, a Turing machine is a theoretical computing system that was proposed by Alan Turing in 1936. A Turing machine capable of efficiently simulating another Turing machine is referred to as a universal Turing machine (hereinafter referred to as the “UTM”). The Church-Turing thesis is characterized by the premise that any practical computation model is equivalent to or has a subset of UTM performance.
A quantum computer is a specific physical system that uses one or more quantum effects in order to perform computation. A quantum computer capable of efficiently simulating another quantum computer is referred to as a universal quantum computer (UQC).
In 1981, Richard P. Feynman stated that quantum computers could be used to more effectively solve a specific computational problem than UTMs and invalidate the Church-Turing thesis. The associated content is described in the paper by R. P. Feynman, “Simulating Physics with Computers,” International Journal of Theoretical Physics, Vol. 21 (1982), pp. 467-488.
For example, Feynman stated that a quantum computer could be used to simulate any other quantum system capable of performing exponentially faster computation for any characteristic property of the simulated quantum system than a UTM.
1. Approaches to Quantum Computation
There are a few general approaches to the design and operation of quantum computers. One approach is the “circuit model” of quantum computation. In this approach, qubits operate in accordance with the sequence of logical gates, which is the representation of a compiled algorithm. Circuit model quantum computers have a few serious barriers in their practical execution. In the circuit model, qubits are required to maintain coherence for a period longer than a single gate time. This requirement is raised because the circuit model quantum computers generally require operations collectively called “quantum error correction” to perform their operations. The quantum error correction cannot be performed without the qubits of circuit model quantum computers capable of maintaining quantum coherence for a period that is about 1,000 times a single gate time. There have been a number of studies that focus on the development of qubits having coherence sufficient to form the basic information units of circuit model quantum computers. The associated content is described in the paper by P. W. Shor, “Introduction to Quantum Algorithms,” arXiv., org: quantph/000 5003 (2001), pp. 1-27. This technical field has still remained stagnant due to lack of the ability to improve the coherence of qubits to the level appropriate to design and operate actual circuit model quantum computers.
2. Qubits
Qubits are used as the basic units of information for quantum computers. Like bits in universal Turing machines (UTMs), qubits can represent at least two different quantities. Qubits may refer to actual physical devices in which information is stored, or may refer to information units themselves which are extracted from the physical devices of the qubits.
Qubits generalize the concept of classical digital bits. A classical information storage device can generally encode two different states that are classified as the labels “0” and “1.” Physically, these two different states are represented by two different, distinct physical states of a classical information storage device, such as the orientation and scale of a magnetic field, a current or a voltage. The quantities adapted to encode bit states follow the laws of classical physics. Furthermore, a qubit may also include two different physical states that are classified as the labels “0” and “1.” Physically, these two different states are represented by two different, distinct physical states of a quantum information storage device, such as the orientation and scale of a magnetic field, a current or a voltage. The quantities adapted to encode bit states follow the laws of quantum physics. If physical quantities storing the above states mechanically operate like quanta, the device may be additionally located in the superposition of “0” and “1.” That is, a qubit can simultaneously exist in states “0” and “1,” and may perform computation in the two states.
3. Superconducting Qubits
In connection with the use of quantum computers, there are many different hardware and software approaches. One hardware approach is to use integrated circuits made of a superconductive material, such as aluminum or niobium.
The technologies and processes included in a process of designing and fabricating superconducting integrated circuits are similar to technologies and processes that are used for conventional integrated circuits.
Superconducting qubits correspond to a type of superconducting devices that can be included in superconducting integrated circuits. Superconducting qubits may be classified into a few categories that are dependent on physical quantities that are used to encode information. For example, superconducting qubits may be classified into charge devices, flux devices and phase devices, which are described in the paper by Makhlin et al., 2001, Reviews of Modern Physics 73, pp. 357-400. The charge devices store and process information regarding the charge states of devices, and unit charges are composed of pairs of electrons called “Cooper pairs.” A Cooper pair includes 2e charges, for example, two electrons bound by phonon interaction. The associated content is described in the paper by Nielsen and Chuang, “Quantum Computation and Quantum Information,” Cambridge University Press, Cambridge 2000, pp. 343-345. The flux devices store information about magnetic flux-related variables via parts of the devices. The phase devices store information regarding variables related to differences in superconductive phase between two regions of the phase devices. Recently, hybrid devices using two or more charges, fluxes and degrees of freedom of phase have been developed. The associated content is described in documents, for example, U.S. Pat. No. 6,838,694 and U.S. patent application Ser. No. 11/082,519 (U.S. Patent Publication No. US 2005/0207718 A1).
4. Computational Complexity Theory
In computer science, computational complexity theory is a type of theory of computation used to research into resources or costs and a type of theory of computation required to solve a given computational problem. The costs are generally measured using abstract parameters called “computational resources,” like time and space. The time refers to the number of steps required to solve a problem, and the space refers to the amount of information required and to be stored or the amount of memory required.
Optimization problems correspond to problems in which one or more objective functions are minimized or maximized for a set of variables, sometimes under the condition of sets of constraints.
For example, a traveling salesman problem (TSP) corresponds to an optimization problem in which, for example, an objective function representative of a distance or costs must be optimized to find an itinerary. This itinerary is encoded as a set of variables representative of an optimized solution to the problem. For example, the problem may be composed of a process of finding the shortest path through which all regions are accurately visited once in the state in which lists of the regions have been given. Other examples of optimization problems include a maximum independent set, integer programming, constraint optimization, factoring, prediction modeling, and k-SAT. These problems correspond to the abstractions of many real-world optimization problems, such as operation research, financial portfolio selection, scheduling, supply management, circuit design, and route optimization. The associated content is described in the paper: “A High-Level Look at Optimization: Past, Present, and Future” e-Optimization.com, 2000.”
Simulation problems generally deal with the simulation of a single system that is performed by another system during a normal time interval. For example, computer simulations include business processes, ecological habitats, protein folding, molecular ground states, and quantum systems. These problems often include a number of various entities different from a complex interrelationship and behavioral rules. Feynman stated that quantum systems could be more efficiently used to simulate some physical systems than UTMs.
Many optimization and simulation problems cannot be solved by using UTMs. Due to this constraint, computation devices capable of solving computational problems beyond the level of UTMs are required. For example, in the field of protein folding, grid computing systems and supercomputers have been used to simulate large protein systems. The associated content is described in the paper by Shirts et al., 2000, Science 290, pp. 1903-1904, and Allen et al., 2001, IBM Systems Journal 40, p. 310. The NEOS solver is an online network solver for optimization problems. When a user submits an optimization problem and selects an algorithm to be used, a central server directs the problem to a computer on a network, on which the selected algorithm can be executed. The associated content is described in the paper by Dolan et al., 2002, SIAM News Vol. 35, p. 6. Other digital computer-based systems and methods for the solution of optimization problems can be found. The associated content is described in documents, for example, the document by Fourer et al., 2001, interfaces 31, pp. 130-150. However, all these methods are limited by the fact that the methods use digital computers, which are UTMs. Accordingly, the limitation of classical computation that imposes undesirable scaling between a problem scale and solving time may be easily encountered.
An example of a technology for solving such optimization problems is described in Korean Patent No. 10-1309677 entitled “Adiabatic Quantum Computation Method.”
This preceding technology is directed to a quantum computation method using a quantum system including a plurality of qubits. The quantum computation method enables quantum annealing adapted to simultaneously track configurations in a superimposed state in order to obtain minimum energy (or costs) finally desired in quantum computing, and employs an adiabatic quantum computation (AQC) technique particularly in order to perform quantum annealing. Furthermore, AQC employs a technique for finally obtaining a solution in a desired target state by generating an adiabatic change of a Hamiltonian from an initial state to the target state.
Although the preceding technology describes the general operation of a quantum computing system for the solution of a complex problem, the selection of an optimized quantum system for the solution of a specific complex problem still remains a significantly important problem in spite of the presence of the preceding technology.